/**
 * 6066. 统计区间中的整数数目
 * https://leetcode.cn/contest/weekly-contest-293/problems/count-integers-in-intervals/
 */

function CountIntervals() {
  this.intervals = [];
  this.value = 0;
}

/**
 * @param {number} target
 * @param {number[]} interval
 */
function compare(target, interval) {
  if (target < interval[0]) {
    return -1;
  }
  if (target > interval[1]) {
    return 1;
  }
  return 0;
}

/**
 * @param {number} target
 * @param {number[][]} intervals
 * @return {number[]}
 */
function find(target, intervals) {
  let left = 0;
  let right = intervals.length - 1;
  while (left <= right) {
    const middle = Math.floor((left + right) / 2);
    const res = compare(target, intervals[middle]);
    if (res === 0) {
      return [middle];
    }
    if (res < 0) {
      if (middle === 0 || compare(target, intervals[middle - 1]) > 0) {
        return [middle - 1, middle];
      }
      right = middle - 1;
    } else {
      left = middle + 1;
    }
  }
  return [intervals.length - 1, intervals.length];
}

/**
 * @param {number} left
 * @param {number} right
 * @return {void}
 */
CountIntervals.prototype.add = function (left, right) {
  if (!this.intervals.length) {
    this.intervals.push([left, right]);
    this.value += (right - left + 1);
    return;
  }
  const leftIntervalsIndexes = find(left, this.intervals);
  if (leftIntervalsIndexes.length > 1 && leftIntervalsIndexes[0] === this.intervals.length - 1) {
    this.intervals.push([left, right]);
    this.value += (right - left + 1);
    return;
  }
  const rightIntervalsIndexes = find(right, this.intervals);
  if (rightIntervalsIndexes.length > 1 && rightIntervalsIndexes[1] === 0) {
    this.intervals.unshift([left, right]);
    this.value += (right - left + 1);
    return;
  }
  const leftIntervalIndex = leftIntervalsIndexes.length === 1 ? leftIntervalsIndexes[0] : leftIntervalsIndexes[1];
  const rightIntervalIndex = rightIntervalsIndexes.length === 1 ? rightIntervalsIndexes[0] : rightIntervalsIndexes[0];
  for (let i = leftIntervalIndex; i <= rightIntervalIndex; i += 1) {
    const interval = this.intervals[i];
    this.value -= (interval[1] - interval[0] + 1);
  }
  const min = Math.min(left, this.intervals[leftIntervalIndex][0]);
  const max = Math.max(right, this.intervals[rightIntervalIndex][1]);
  this.intervals.splice(leftIntervalIndex, rightIntervalIndex - leftIntervalIndex + 1, [min, max]);
  this.value += (max - min + 1);
};

/**
 * @return {number}
 */
CountIntervals.prototype.count = function () {
  return this.value;
};

const instance = new CountIntervals();
instance.add(2, 3);
instance.add(7, 10);
console.log(instance.count() === 6);
instance.add(5, 8);
console.log(instance.count() === 8);
